Деление многочленов с остатком

Пусть $F$ — поле, $f, g \in F[x]$ и $g \neq 0$. Тогда существуют однозначно определенные многочлены $q, r \in F[x]$ такие, что $$f = qg + r \quad \text{и} \quad \deg r < \deg g.$$ Многочлен $q$ называется ***(неполным) частным***, а $r$ – ***остатком*** от деления $f$ на $g$. Если $r=0$, то $g$ делит $f$.

**Существование $q, r$** Индукция по $n = \deg f$. *База индукции* ($n = 1$): Если $\deg f < \deg g$, то $q=0, r=f$. *Шаг индукции:* Пусть $\deg f \ge \deg g$. Пусть $f = a_n x^n + \dots$ и $g = b_m x^m + \dots$. Определим $f_1 = f - \dfrac{a_n}{b_m} x^{n-m} g$. Тогда $\deg f_1 < n$. По предположению индукции, существуют $q_1, r_1$ такие, что $f_1 = q_1 g + r_1$ и $\deg r_1 < \deg g$. Тогда $f = \left(\dfrac{a_n}{b_m} x^{n-m} + q_1\right) g + r_1$. Полагаем $q = \dfrac{a_n}{b_m} x^{n-m} + q_1$ и $r=r_1$. **Единственность $q, r$** Пусть $f = q_1g+r_1 = q_2g+r_2$, где $\deg r_1 < \deg g$ и $\deg r_2 < \deg g$. Тогда $(q_1-q_2)g = r_2-r_1$. Если $q_1 \neq q_2$, то $\deg((q_1-q_2)g) \ge \deg g$. Однако $\deg(r_2-r_1) < \deg g$. Это противоречие. Следовательно, $q_1-q_2=0 \implies q_1=q_2$, и тогда $r_2-r_1=0 \implies r_1=r_2$. $\square$